package dac.fibonacci.core;

import java.math.BigDecimal;

/**
 * 矩阵相乘法求Fibonacci
 * 期望时间T(n)=θ(lgn)
 * */
public class FibonacciByMatrix implements Fibonacci{
	
	private BigDecimal[][] baseMat;
	
	public FibonacciByMatrix(){
		baseMat = new BigDecimal[][]{
				{new BigDecimal("1"), new BigDecimal("1")},
				{new BigDecimal("1"), new BigDecimal("0")}};
	}

	public BigDecimal get(int n) throws Exception {
		return getMatrixN(n)[1][0];
	}
	
	private BigDecimal[][] getMatrixN(int n) throws Exception{
		if(n <= 0){
			throw new Exception("N must be greater than zero");
		}
		if(n == 1){
			return baseMat;
		}
		
		if(n % 2 == 0){
			BigDecimal[][] matNover2 = getMatrixN(n/2);
			return multi(matNover2, matNover2);
		} else {
			BigDecimal[][] matNMinusOneover2 = getMatrixN((n-1)/2);
			BigDecimal[][] matTemp = multi(matNMinusOneover2, matNMinusOneover2);
			return multi(matTemp, baseMat);
		}
	}
	
	private BigDecimal[][] multi(BigDecimal[][] a, BigDecimal[][] b){
		BigDecimal[][] c = new BigDecimal[2][2];
		c[0][0] = a[0][0].multiply(b[0][0]).add(a[0][1].multiply(b[1][0]));
		c[0][1] = a[0][0].multiply(b[0][1]).add(a[0][1].multiply(b[1][1]));
		c[1][0] = a[1][0].multiply(b[0][0]).add(a[1][1].multiply(b[1][0]));
		c[1][1] = a[1][0].multiply(b[0][1]).add(a[1][1].multiply(b[1][1]));
		return c;
	}

}
